#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : SplitArrayConsecutiveSubseq.py
# @Time    : 2020/12/4 10:25
# @Description:
from typing import List
from collections import defaultdict, Counter
import heapq


class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        """
        Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more
        subsequences such that each subsequence consists of consecutive integers and has length at least 3.

        Example 1:
            Input: [1,2,3,3,4,5]
            Output: True
            Explanation:
            You can split them into two consecutive subsequences :
                1, 2, 3
                3, 4, 5
        Example 2:
            Input: [1,2,3,3,4,4,5,5]
            Output: True
            Explanation:
            You can split them into two consecutive subsequences :
                1, 2, 3, 4, 5
                3, 4, 5
        Example 3:
            Input: [1,2,3,4,4,5]
            Output: False

        Constraints:
            - 1 <= nums.length <= 10000

        :param nums:
        :return:
        """
        mp = defaultdict(list)
        for x in nums:
            queue = mp.get(x - 1)
            if queue:
                prevLength = heapq.heappop(queue)
                heapq.heappush(mp[x], prevLength + 1)
            else:
                heapq.heappush(mp[x], 1)

        return not any(queue and queue[0] < 3 for queue in mp.values())

    def isPossible2(self, nums: List[int]) -> bool:
        count_map = Counter(nums)
        end_map = Counter()

        for x in nums:
            count = count_map[x]
            if count > 0:
                prev_end_count = end_map.get(x - 1, 0)
                if prev_end_count > 0:
                    count_map[x] -= 1
                    end_map[x - 1] = prev_end_count - 1
                    end_map[x] += 1
                else:
                    count1 = count_map.get(x + 1, 0)
                    count2 = count_map.get(x + 2, 0)
                    if count1 > 0 and count2 > 0:
                        count_map[x] -= 1
                        count_map[x + 1] -= 1
                        count_map[x + 2] -= 1
                        end_map[x + 2] += 1
                    else:
                        return False
        return True


if __name__ == '__main__':
    S = Solution()
    nums = [1, 2, 3, 3, 4, 4, 5, 5]
    print(S.isPossible(nums))
    print(S.isPossible2(nums))
    print('done')
